This invention relates to a high-speed packet-switching system.
Packet-switched networks are widely employed in data communications because they economically utilize communication channel resources; they require the sending and receiving terminals to be connected only when data are actually being transmitted, not during the idle periods between transmissions. Specifically, data are transmitted in packets, each containing the address of the receiving terminal. The packet switch in the network must be capable of reading the address in each packet and quickly routing the packet to the correct destination.
One well-known design for a high-speed packet switch employs a self-routing switching network comprising a plurality of 2.times.2 crosspoint switching elements that operate according to individual bits in the packet address. The switching elements are so interconnected as to ensure that a packet will automatically be routed to the correct address, provided no collisions with other packets occur en route.
A problem with this packet switch design is that when collisions do occur, one of the two colliding packets is routed to the wrong address. A prior-art solution to this problem is to provide a sorting network or trap network to sort or otherwise preprocess the packets before they enter the self-routing switching network. In this way it is possible to ensure that packets destined for different addresses will be routed correctly, without colliding. This scheme does not, however, solve the problem of multiple packets having the same destination address. Such packets still collide, with the result that some of them are routed to the wrong address.